{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ch04 Python中的字典与集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## python中其他数据结构"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 堆数据结构"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> headq是python内置的一种数据结构\n",
    ">它是一种优先队列。优先队列让你能够以任意顺序添加对象，并随时（可能是在两次添加对象之间）找出（并删除）最小的元素。相比于列表方法min，这样做的效率要高得多。\n",
    "实际上，Python没有独立的堆类型，而只有一个包含一些堆操作函数的模块。这个模块名为heapq（其中的q表示队列），它包含6个函数，其中前4个与堆操作直接相关。必须使用列表来表示堆对象本身。\n",
    "\n",
    "#### 模块heapq中一些重要的函数\n",
    "| 函 数  |  描 述|\n",
    "|--|--|\n",
    "| heappush(heap, x)   |    将x压入堆中|\n",
    "| heappop(heap)       |   从堆中弹出最小的元素|\n",
    "| heapify(heap)         |    让列表具备堆特征|\n",
    "| heapreplace(heap, x)      |   弹出最小的元素，并将x压入堆中|\n",
    "| nlargest(n, iter)        |       返回iter中n个最大的元素|\n",
    "|nsmallest(n, iter)         |      返回iter中n个最小的元素|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 1, 2, 9, 3, 8, 4, 0, 7, 6]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import heapq  \n",
    "import random\n",
    "data=list(range(10))\n",
    "random.shuffle(data)\n",
    "data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 5, 8, 4, 9, 7, 6]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heap=[]\n",
    "for n in data:\n",
    "    heapq.heappush(heap,n)\n",
    "heap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0.5, 2, 3, 1, 8, 4, 9, 7, 6, 5]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappush(heap,0.5)\n",
    "heap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 6, 5, 8, 7, 9]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5, 4, 6, 9, 8, 7]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(heap)\n",
    "heap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `heapify()`列表堆化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 7, 8, 9, 5, 10, 333]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myheap = [1,2,3,5,7,8,9,4,10,333]\n",
    "heapq.heapify(myheap)\n",
    "myheap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `heapreplace()`函数，每次弹出最小的，压入指定元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 4, 3, 5, 7, 8, 9, 6, 10, 333]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heapreplace(myheap,6)\n",
    "myheap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `nlargest()`返回堆中最大的三个元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[333, 10, 9]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.nlargest(3,myheap)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `nsmallest`返回堆中最小的三个元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.nsmallest(3,myheap)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 堆的应用——堆排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def heapsort(iterable):\n",
    "    h = []\n",
    "    for value in iterable:\n",
    "        heapq.heappush(h, value)\n",
    "    return [heapq.heappop(h) for i in range(len(h))] #通过列表推导式，将堆的弹出元素添加到列表中\n",
    "\n",
    "heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])\n",
    "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 队列数据结构\n",
    "\n",
    "- [quene队列参考资料](https://www.cnblogs.com/dbf-/p/11118628.html)\n",
    "- [quene队列参考资料](https://www.jianshu.com/p/3e422a96b008)\n",
    "- [python 生成器 & 迭代器](https://www.cnblogs.com/dbf-/p/11877251.html)\n",
    "\n",
    "##### queue 模块\n",
    "- `queue` 模块中有 `Queue` 类，`LifoQueue`、`PriorityQueue` 都继承了 Queue\n",
    "\n",
    "- `maxsize`\n",
    "    - maxsize 是实例化 Queue 类时的一个参数，默认为 0\n",
    "    - Queue(maxsize=0) 可以控制队列中数据的容量\n",
    "\n",
    "- `put`\n",
    "    - Queue.put(block=True, timeout=None)\n",
    "    - block 用于设置是否阻塞， timeout 用于设置阻塞时等待时长\n",
    "    - put_nowait() = put(block=False)\n",
    "\n",
    "- **阻塞**\n",
    "    - 当队列满了之后，put 就会阻塞，一直等待队列不再满时向里面添加数据\n",
    "\n",
    "- **不阻塞**\n",
    "- 当队列满了之后，如果设置 put 不阻塞，或者等待时长到了之后会报错：queue.Full\n",
    "\n",
    "- `get`\n",
    "    - Queue.get(block=True, timeout=None)\n",
    "    - get_nowait() = get(block=False)\n",
    "\n",
    "- **阻塞**\n",
    "    - 当队列空了之后，get 就会阻塞，一直等待队列中有数据后再获取数据\n",
    "\n",
    "- **不阻塞**\n",
    "    - 当队列空了之后，如果设置 get 不阻塞，或者等待时长到了之后会报错：_queue.Empty\n",
    "\n",
    "- **full & empty**\n",
    "    - `Queue.empty()`、`Queue.full() `用于判断队列是否为空、满; 尽量使用 `qsize `代替\n",
    "\n",
    "- **qsize**\n",
    "Queue.qsize() 用于获取队列中大致的数据量\n",
    "注意：在多线程的情况下不可靠\n",
    "因为在获取 qsize 时，其他线程可能又对队列进行操作了\n",
    "\n",
    "- **join**\n",
    "join 会在队列存在未完成任务时阻塞，等待队列无未完成任务，需要配合 task_done 使用\n",
    "\n",
    "- **task_done**\n",
    "执行一次 put 会让未完成任务 +1 ，但是执行 get 并不会让未完成任务 -1 ，需要使用 task_done 让未完成任务 -1 ，否则 join 就无法判断\n",
    "队列为空时执行会报错：ValueError: task_done() called too many times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "2\n",
      "2\n",
      "2queue is empty now\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import queue\n",
    "import threading\n",
    "import time\n",
    "\n",
    "\n",
    "def q_put():\n",
    "    for i in range(10):\n",
    "        q.put('1')\n",
    "    while True:\n",
    "        q.put('2')\n",
    "        time.sleep(1)\n",
    "\n",
    "\n",
    "def q_get():\n",
    "    while True:\n",
    "        temp = q.get()\n",
    "        q.task_done()\n",
    "        print(temp)\n",
    "        time.sleep(0.3)\n",
    "\n",
    "\n",
    "q = queue.Queue()\n",
    "t1 = threading.Thread(target=q_put)\n",
    "t2 = threading.Thread(target=q_get)\n",
    "t1.start()\n",
    "t2.start()\n",
    "q.join()\n",
    "print('queue is empty now')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "import queue #queue in python3\n",
    "q1=queue.Queue()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 第一种：FIFO (先入先出)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 入队\n",
    "- `0`--->`0`--->`1`--->`2`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([0, 0])\n"
     ]
    }
   ],
   "source": [
    "q1.put(0)\n",
    "q1.put(0)\n",
    "print(q1.queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([0, 0, 1])\n"
     ]
    }
   ],
   "source": [
    "q1.put(1)\n",
    "print(q1.queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "deque([0, 0, 1, 2])\n"
     ]
    }
   ],
   "source": [
    "q1.put(2)\n",
    "print(q1.queue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 出队\n",
    "- `0`--->`0`--->`1`--->`2`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "deque([0, 1, 2])\n"
     ]
    }
   ],
   "source": [
    "print(q1.get())\n",
    "print(q1.queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "deque([1, 2])\n"
     ]
    }
   ],
   "source": [
    "print(q1.get())\n",
    "print(q1.queue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 第二种：LIFO (后入先出)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n"
     ]
    }
   ],
   "source": [
    "q2 = queue.LifoQueue()\n",
    "q2.put(1)\n",
    "print(q2.queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5]\n"
     ]
    }
   ],
   "source": [
    "q2.put(5)\n",
    "print(q2.queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 3]\n"
     ]
    }
   ],
   "source": [
    "q2.put(3)\n",
    "print(q2.queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "[1, 5]\n"
     ]
    }
   ],
   "source": [
    "elem = q2.get()  #LIFO\n",
    "print(elem)\n",
    "print(q2.queue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 第三种：优先级队列（数据可设置优先级）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 5, 7, 9]\n",
      "3\n",
      "5\n",
      "7\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "import queue\n",
    "q_pq = queue.PriorityQueue()\n",
    "\n",
    "#数值越大，权重越高\n",
    "q_pq.put(3, 10)\n",
    "q_pq.put(9, 5)\n",
    "q_pq.put(7, 2)\n",
    "q_pq.put(5, 1)\n",
    "\n",
    "print(q_pq.queue)\n",
    "\n",
    "for i  in range(4):\n",
    "    print(q_pq.get())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, '1')\n",
      "(1, 'a')\n",
      "(2, '2')\n",
      "(3, '3')\n"
     ]
    }
   ],
   "source": [
    "import  queue\n",
    "q = queue.PriorityQueue()\n",
    "q.put((2, '2'))\n",
    "q.put((1, '1'))\n",
    "q.put((3, '3'))\n",
    "q.put((1, 'a'))\n",
    "\n",
    "print(q.get())\n",
    "print(q.get())\n",
    "print(q.get())\n",
    "print(q.get())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 生产者和消费者模式\n",
    "- 生产者消费者模型（主要用于解耦）\n",
    ">在多线程开发当中，如果生产线程处理速度很快，而消费线程处理速度很慢，那么生产线程就必须等待消费线程处理完，才能继续生产数据。同样的道理，如果消费线程的处理能力大于生产线程，那么消费线程就必须等待生产线程。为了解决这个问题于是引入了生产者和消费者模式\n",
    "生产者消费者模式是通过一个容器来解决生产者和消费者的强耦合问题。生产者和消费者彼此之间不直接通讯，而通过阻塞队列来进行通讯，所以生产者生产完数据之后不用等待消费者处理，直接扔给阻塞队列，消费者不找生产者要数据，而是直接从阻塞队列里取，阻塞队列就相当于一个缓冲区，平衡了生产者和消费者的处理能力。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import threading\n",
    "import time\n",
    "import queue\n",
    "\n",
    "\n",
    "def producer():\n",
    "    count = 1\n",
    "    while 1:\n",
    "        q.put('No.%i' % count)\n",
    "        print('Producer put No.%i' % count)\n",
    "        time.sleep(1)\n",
    "        count += 1\n",
    "\n",
    "\n",
    "def customer(name):\n",
    "    while 1:\n",
    "        print('%s get %s' % (name, q.get()))\n",
    "        time.sleep(1.5)\n",
    "\n",
    "\n",
    "q = queue.Queue(maxsize=5)\n",
    "p = threading.Thread(target=producer, )\n",
    "c = threading.Thread(target=customer, args=('jack', ))\n",
    "p.start()\n",
    "c.start()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 双端队列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque(['Eric', 'John', 'Michael'])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import deque\n",
    "queue = deque([\"Eric\", \"John\", \"Michael\"])\n",
    "queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque(['Eric', 'John', 'Michael', 'Terry'])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queue.append(\"Terry\") \n",
    "queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque(['Eric', 'John', 'Michael', 'Terry', 'Graham'])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queue.append(\"Graham\")\n",
    "queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque(['John', 'Michael', 'Terry', 'Graham'])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queue.popleft() \n",
    "queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque(['John', 'Michael', 'Terry'])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queue.pop() #从右端弹出\n",
    "\n",
    "queue "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 自定义数据结构"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "os.chdir(\"../ds/\")\n",
    "import myQueue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The queue is empty\n"
     ]
    }
   ],
   "source": [
    "q=myQueue.myQueue() #初始化\n",
    "q.get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 7]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#The queue is empty\n",
    "q.put(5)\n",
    "q.put(7)\n",
    "q.show()\n",
    "q.isFull()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 7, 'a', 3]\n"
     ]
    }
   ],
   "source": [
    "q.put('a')\n",
    "q.put(3)\n",
    "q.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 7, 'a']\n"
     ]
    }
   ],
   "source": [
    "q.setSize(3)\n",
    "q.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The queue is full\n"
     ]
    }
   ],
   "source": [
    "q.put(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 7, 'a']\n"
     ]
    }
   ],
   "source": [
    "q.setSize(5)\n",
    "q.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 7, 'a', 10]\n"
     ]
    }
   ],
   "source": [
    "q.put(10)\n",
    "q.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 通过列表实现栈"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5, 7]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myStack = []\n",
    "myStack.append(3)\n",
    "myStack.append(5)\n",
    "myStack.append(7)\n",
    "myStack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myStack.pop() #LIFO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myStack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myStack.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 栈数据结构"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "E:\\deeplearning\\ds\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "print(os.getcwd())\n",
    "# os.chdir(\"../ds/\")\n",
    "import Stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = Stack.Stack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.isEmpty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.isFull()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5]\n"
     ]
    }
   ],
   "source": [
    "s.push(5)\n",
    "s.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 8]\n"
     ]
    }
   ],
   "source": [
    "s.push(8)\n",
    "s.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 8, 'a']\n"
     ]
    }
   ],
   "source": [
    "s.push('a')\n",
    "s.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 8]\n"
     ]
    }
   ],
   "source": [
    "s.pop()\n",
    "s.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 8, 'b', 'c']\n"
     ]
    }
   ],
   "source": [
    "s.push('b')\n",
    "s.push('c')\n",
    "s.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stack can still PUSH  6  elements.\n"
     ]
    }
   ],
   "source": [
    "s.showRemainderSpace()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.setSize(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.isFull()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 8, 'b']\n"
     ]
    }
   ],
   "source": [
    "s.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stack Full!\n",
      "[5, 8, 'b', 'd', 'dddd']\n"
     ]
    }
   ],
   "source": [
    "s.setSize(5)\n",
    "s.push('d')\n",
    "s.push('dddd')\n",
    "s.push(3)\n",
    "s.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 链表数据结构\n",
    " - 直接用`list'`实现\n",
    " - 时间复杂度可以参考list的函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "linkTable = []\n",
    "linkTable.append(3)\n",
    "linkTable.append(5)\n",
    "linkTable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 插入元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 5]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "linkTable.insert(1,4)\n",
    "linkTable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "linkTable.remove(4)\n",
    "linkTable.remove(linkTable[1])\n",
    "linkTable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二叉树数据结构"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "# os.chdir(\"../ds/\")\n",
    "import BinaryTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root\n"
     ]
    }
   ],
   "source": [
    "root = BinaryTree.BinaryTree('root')\n",
    "root.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root\n"
     ]
    }
   ],
   "source": [
    "firstLeft = root.insertLeftChild('A')\n",
    "root.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "D\n",
      "C\n",
      "A\n",
      "B\n",
      "root\n",
      "C\n",
      "D\n",
      "A\n",
      "root\n",
      "B\n"
     ]
    }
   ],
   "source": [
    "firstRight = root.insertRightChild('B')\n",
    "secondLeft = firstLeft.insertLeftChild('C')\n",
    "thridRight = secondLeft.insertRightChild('D')\n",
    "root.postOrder()\n",
    "root.inOrder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
